//给你一个链表，两两交换其中相邻的节点，并返回交换后链表的头节点。你必须在不修改节点内部的值的情况下完成本题（即，只能进行节点交换）。
// 示例 1：
//输入：head = [1,2,3,4]
//输出：[2,1,4,3]
// 示例 2：
//输入：head = []
//输出：[]
// 示例 3：
//输入：head = [1]
//输出：[1]
// 提示：
// 链表中节点的数目在范围 [0, 100] 内
// 0 <= Node.val <= 100
// Related Topics 递归 链表 👍 1292 👎 0

package leetcode.editor.cn;

class SwapNodesInPairs {
    public static void main(String[] args) {
        Solution solution = new SwapNodesInPairs().new Solution();
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    //  Definition for singly-linked list.
    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

    class Solution {
        /**
         *  虚拟头节点法
         * @param head
         * @return
         */
        /*
        public ListNode swapPairs(ListNode head) {
            // 虚拟头节点
            ListNode dummyNode = new ListNode(0);
            dummyNode.next = head;
            ListNode pre = dummyNode;
            ListNode tmp = null;    // 临时节点

            // 注意判断只有一个节点的情况，所以head.next也需要判断
            // 也可以使用pre.next != null && pre.next.next != null判断
            while (head != null && head.next != null) {
                tmp = head.next.next;
                pre.next = head.next;
                head.next.next = head;
                head.next = tmp;

                // 向后移动
                pre = head;
                head = tmp;
            }

            return dummyNode.next;
        }
         */

        /**
         * 递归法（从右到左）
         *
         * @param head
         * @return
         */
        /*public ListNode swapPairs(ListNode head) {
            // 递归结束的条件
            if (head == null || head.next == null) {
                return head;
            }

            // 获取头结点的下一个节点
            ListNode nextNode = head.next;
            // 调用递归进行循环
            ListNode newNode = swapPairs(nextNode.next);
            // 转换指针指向
            nextNode.next = head;
            head.next = newNode;

            // 返回nextNode用来连接上一个节点
            return nextNode;
        }*/

        // 虚拟头节点法
        /*public ListNode swapPairs(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode pre = head, cur = head.next, temp = dummy;
            while (cur != null && cur.next != null) {
                ListNode tmp = cur.next;
                pre.next = cur.next;
                cur.next = pre;
                temp.next = cur;
                temp = pre;
                pre = tmp;
                cur = tmp.next;
            }

            if (cur != null) {
                cur.next = pre;
                pre.next = null;
                temp.next = cur;
            }

            return dummy.next;
        }*/

        // 递归版
        /*public ListNode swapPairs(ListNode head) {
            // head.next 和 head 都有必要判断，会出现个数为奇偶的情况
            // 终止条件
            if (head == null && head.next == null) return head;

            ListNode next = head.next;

            // 递归到最后
            ListNode newNode = swapPairs(next.next);

            next.next = head;
            head.next = newNode;

            return next;
        }*/

        /*public ListNode swapPairs(ListNode head) {
            if (head == null || head.next == null) return head;
            ListNode dummy = new ListNode(0);
            dummy.next = head;
            ListNode pre = dummy, cur = head;
            while (cur != null && cur.next != null) {
                ListNode next = cur.next.next;
                pre.next = cur.next;
                cur.next.next = cur;
                cur.next = next;
                pre = cur;
                cur = next;
            }

            return dummy.next;
        }*/

        // 递归版本
        public ListNode swapPairs(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }

            ListNode next = head.next.next;
            head.next.next = head;
            ListNode temp = head.next;
            head.next = swapPairs(next);

            return temp;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
